{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 堆和heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 文章目的\n",
    "\n",
    "# 掌握堆这种数据结构：堆这种数据结构在本科的算法课上老师就讲过，这次做一下总结\n",
    "# heapq是python的堆模块，它有一些特别的用法，学会这些用法，让自己的编程Pythonic多一丢丢"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 堆：\n",
    "\n",
    "# 堆的最原本定义应该是不受树的分叉的影响，只要满足节点值单调就行。\n",
    "# 即对于任何节点，父节点的值永远小于等于子节点的值或者永远大于等于子节点的值。\n",
    "# 但是，如果不限制分叉数的话，整个堆是杂乱无章的，既不好构建又不好维护。\n",
    "# 因此，我们谈论堆的时候，默认谈论二叉堆。\n",
    "\n",
    "# 堆通常是一个可以被看做一棵完全二叉树的数组对象。\n",
    "# 这句话是精髓，表明堆的结构是一颗完全二叉树，只是可以用数组来存。这道理和leetcode上给的树的表达形式很类似。\n",
    "# 所以取最小堆的root，或者说min_heap[0]就可以获取堆中最小值，而且等下堆又自己维护好了顺序。最大堆同理。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "## heapq\n",
    "\n",
    "# heapq是python的堆的一个模块。\n",
    "# 索引值从0开始。\n",
    "# 每个节点和左右子节点的索引数学关系:(2k+1,2K+2)\n",
    "# 最小堆，pop方法弹出最小值\n",
    "# 创建一个堆：h=[]，heapq.heappush(h,sth)。\n",
    "# 小细节,这个sth可以是packing的结果，之后堆的维护会按照pachking中第一个元素维护。\n",
    "# 其他位置上的元素可以是辅助信息，比如索引。heapq.heappush(h,(your_list[index],index))\n",
    "# 其他有关堆的操作，详见API\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 编程实例：1289. 下降路径最小和  II\n",
    "\n",
    "# 这本是我在leetcode上练习的一道DP的问题，做优化的时候利用到了堆。\n",
    "# 详见leetcode。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在java中，对应PriorityQueue()，一摸一样。"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "fcde990f9140614acfcf011c3251f5c500b1a43ee1bc68457481590075bcff1b"
  },
  "kernelspec": {
   "display_name": "Python 3.9.5 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
